from tools_algorithm import *


def palindromesIntegers(limit=10000):
    b = 1
    pi = []  # 回文整数
    while b <= limit:
        for i in range(b, b * 10):
            c, t = i, i // 10
            while t > 0:
                c = c * 10 + t % 10
                t //= 10
            pi.append(c)
        if b < limit:
            for i in range(b, b * 10):
                c, t = i, i
                while t > 0:
                    c = c * 10 + t % 10
                    t //= 10
                pi.append(c)
        b *= 10
    return pi


def isIntegerPalindromes(num):
    t, b, c = num, 1, 1
    while t > 9:
        t, b, c = t // 10, b * 10, c + 1
    t = num
    for _ in range(c // 2):
        if t // b % 10 != num % 10:
            return False
        b, num = b // 10, num // 10
    return True


pi = palindromesIntegers()
spi = []
for p in pi:
    pp = p * p
    if isIntegerPalindromes(pp):
        spi.append(pp)


class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        return bisect_left(spi, int(right)) - bisect_left(spi, int(left))


s = Solution()

print(s.superpalindromesInRange(1, 2))
print(s.superpalindromesInRange("10086", "177854122662"))
